题目描述
leetcode 第227题:基本计算器 II
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例:
输入:s = “ 3+5 / 2 “
输出:5
解题方法
栈
参照题解
- 解题思路
由于字符串表达式
s
中存在空格,需要先去除空格,这时s
中仅存在数字、加减乘除号
然后定义变量sign
来标示每个数前面的运算符
对于s
,第一个数前面的符号一定为正,3+5看作0+3+5,所以sign
默认为+
,
先计算乘除后整体转换为加法运算,创建栈stack
存储每次需要相加的数值
获取s
的长度n
,在[0,n)
的范围内循环得到当前字符s[i]
如果s[i]
为数字,计算当前数字的数值num
如果s[i]
为运算符或者下标i
等于n-1
(保证末尾数字参与运算)时
分别考虑以下情况:s[i]
为+
号,num
压栈s[i]
为-
号,负的num
压栈s[i]
为*
号,计算num
与栈顶元素相乘的结果后压栈s[i]
为/
号,计算num
与栈顶元素相除的结果后压栈
每次压栈后,更新sign
为当前的运算符并将num
清零
最后将栈stack
中元素求和,即为s
计算后的值
- 复杂度
时间复杂度:O(n),n为字符串s的长度
空间复杂度:O(n),n为字符串s的长度
python3
1 | class Solution: |
php
1 | class Solution { |